/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

import java.util.Stack;

/**
 * <p>
 * 最长有效括号 给定一个字符串只包含圆括号，找出最长合法括号子串的长度
 * 
 * For "(()", the longest valid parentheses substring is "()", which has length = 2.
 * 
 * Another example is ")()())", where the longest valid parentheses substring is "()()", which has
 * length = 4.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月24日
 */
public class LongestValidParentheses {
    //使用栈记录为配对的情况，还要考虑尚未配对的左括号的下标
 public int longestValidParentheses(String s) {
        int maxLen  = 0;
        Stack<Integer> stack  = new Stack<>();
        //记录有效配对的开始下标
        int left = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                if(stack.isEmpty()){
                    left = i+1;
                }else{
                    stack.pop();
                    // 有效配对的开始位置视栈是否为空而定
                    if(stack.isEmpty()){
                        maxLen = Math.max(maxLen, i-left+1);
                    }else{
                        //非空，则长度取决于栈顶的下标
                        maxLen = Math.max(maxLen,i-stack.peek());
                    }
                }
            }
        }
        return maxLen;
    }
 public static void main(String[] args) {
    String s  = "(()";
    System.out.println(new LongestValidParentheses().longestValidParentheses(s));
    
    s  = ")()())";
    System.out.println(new LongestValidParentheses().longestValidParentheses(s));
}
}
